//给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。 
//
// 编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。 
//
// 示例 1： 
//
// 
//输入：
//beginWord = "hit",
//endWord = "cog",
//wordList = ["hot","dot","dog","lot","log","cog"]
//
//输出：
//["hit","hot","dot","lot","log","cog"]
// 
//
// 示例 2： 
//
// 
//输入：
//beginWord = "hit"
//endWord = "cog"
//wordList = ["hot","dot","dog","lot","log"]
//
//输出：[]
//
//解释：endWord "cog" 不在字典中，所以不存在符合要求的转换序列。 
//
// Related Topics 广度优先搜索 哈希表 字符串 回溯 👍 77 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-09-16 23:43:18
 * @description 面试题 17.22.单词转换
 */
public class WordTransformerLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 WordTransformerLcci fun=new WordTransformerLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> findLadders1(String beginWord, String endWord, List<String> wordList) {
		List<String> result = new ArrayList<>();
		result.add(beginWord);
		boolean [] vis=new boolean[wordList.size()];
		if (!wordList.contains(endWord)) {
			return new ArrayList<>();
		}
		if(hasRoute(beginWord, endWord, wordList, vis, result)){
			return result;
		}
		return new ArrayList<>();
    }
	boolean canTranslate(String from, String to){
		if(from.length() != to.length()) { return false; }
		int count = 0;
		for(int i = 0; i < from.length(); ++i){
			if(from.charAt(i) != to.charAt(i)) {
				count++;
			}
		}
		return count == 1;
	}

	boolean hasRoute(String curWord, String endWord,List<String> wordList,
				  boolean[] visited, List<String> result) {
		if (curWord.equals(endWord)) {
			return true;
		}
		for(int i = 0; i < wordList.size(); ++i){
			if(visited[i] || !canTranslate(curWord, wordList.get(i))) continue;
			visited[i] = true;
			result.add(wordList.get(i));
			if(hasRoute(wordList.get(i), endWord, wordList, visited, result)){
				return true;
			}
			result.remove(result.size()-1);
			// 如果运行到这一步，意味着无法从i这个点找到路径，所以visited[i]无需改为false.
			// visited[i] = false;
		}
		return false;
	}

	public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
		List<String> list = new ArrayList<>();
		Set<String> set = new HashSet<>(wordList);
		if(!set.contains(endWord)) {
			return list;
		}
		Queue<List<String>> queue = new ArrayDeque<>();
		list.add(beginWord);
		queue.add(list);
		set.remove(beginWord);
		while (!queue.isEmpty()) {
			int size = queue.size();
			while (size > 0) {
				List<String> curPath = queue.poll();
				String curWord = curPath.get(curPath.size() - 1);
				//找出当前路径的下个词
				for (int i = 0; i < curWord.length(); i++) {
					char[] ch = curWord.toCharArray();
					char temp = ch[i];
					for (char j = 'a'; j <= 'z'; j++) {
						if (j == temp) {
							continue;
						}
						//改变每个位上的所有字母找到可以走的路径
						ch[i] = j;
						String nextWord = new String(ch);
						// 如果这个路没有走过，加入路径
						if (set.contains(nextWord)) {
							List<String> newPath = new ArrayList<>(curPath);
							newPath.add(nextWord);
							// 不要走环，而且每次都是第一次就移除，如果是从其他地方访问过来的，那么其他地方最短，当前是最长的
							set.remove(nextWord);
							// 到终点直接返回
							if (nextWord.equals(endWord)) {
								return newPath;
								// 否则加入队列
							} else {
								queue.add(newPath);
							}
						}
					}
					// 恢复原单词
					ch[i] = temp;
				}
				size--;
			}
		}
		return new ArrayList<>();
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
